Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
/
ЗВІТ
З лабораторної роботи №1
з дисципліни:
«Алгоритми та методи обчислень»
на тему:
«Алгоритм, властивості, параметри та характеристики складності алгоритму»
Мета роботи: засвоїти основні поняття та визначення теорії алгоритмів, проаналізувати вплив параметрів алгоритму на характеристики складності алгоритму
Теоретична частина
Опис алгоритму
Маючи два натуральні числа a та b:
якщо b=0, то a є шуканим НСД,
інакше повторюємо обчислення для пари b та залишку від ділення a на b (тобто a mod b).
Версія ітераційна:
НСД( a, b)
поки b ≠ 0
c := остача від ділення a на b
a := b
b := c
поверни a
Версія рекурсивна:
НСД( a, b)
якщо b = 0
поверни a
інакше
поверни НСД( b, остача від ділення a на b)
Для того, щоб довести ефективність алгоритму, потрібно порівняти його з таким, який
приймається за неефективний. Прикладом такого неефективного алгоритму є процедура послідовного перебору можливих розв’язань задачі. Будемо вважати, що алгоритм перебору утворений в результаті структурного синтезу, на основі вхідних даних та намагання знайти серед всіх допустимих чисел такє, що є найбільшим дільником двох заданих чисел.
Ефективність, як правило, визначається такою характеристикою як часова складність, що вимірюється кількістю операцій, необхідних для розв’язання задачі.
Дослідимо розв’язання задачі знаходження найбільшого спільного дільника двох цілих чисел (N1>0,N2 >0, N1≥N2 ) алгоритмом перебору і алгоритмом Евкліда.[10] Алгоритм перебору заснований на операції інкременту змінної (n) від одиниці до меншого (N2) з двох заданих чисел і перевірці, чи ця змінна є дільником заданих чисел. Якщо це так, то значення змінної запам’ятовується і операції алгоритму продовжуються. Якщо ні, то операції алгоритму продовжуються без запам’ятовування. Операції алгоритму закінчуються видачею з пам’яті знайденого останнім спільного дільника. Блок-схема алгоритму приведена на рис.2(а).
a) б)
Рис2. Блок-схема алгоритму перебору (а) і Евкліда (б).
Послідовність виконання роботи
Користуючись програмою Lab_NSD.exe знайшли два числа з діапазону [1, 150], для яких часова складність алгоритму Евкліда найбільша, L=7, це числа 129 і 49.
Текст програми:
#include <iostream>
using namespace std;
int NSD1(int N1,int N2,int L2)
{
if(N2==0){
cout<<"L2="<<L2<<endl;
return N1;}
else
{L2++;
return NSD1(N2, N1%N2,L2);}
cout<<"L2="<<L2<<endl;
}
int main()
{
int N1,a,b,N2,k,i,NSD,r,n,L1=0,L2=0,L3=0,f,s;
char r1='l';
cout<<"Diapazon:";
cin>>a;cout<<endl;cin>>b;cout<<endl;
while(1){
char r1='l';
N1=a+rand()%(b-a);
N2=a+rand()%(b-a);
cout<<"First number: "<<N1<<endl<<"Second number: "<<N2<<endl;
k=min(N1,N2);
i=1;
NSD=i;
do{
i++;
if (((N1%i)==0) & ((N2%i)==0))
NSD=i;L1=L1+1;
} while(i<=k);
cout<<"NSD za I metodom:"<<NSD<<endl<<"L1="<<L1<<endl;
cout<<"NSD za II metodom:"<<NSD1(N1,N2,L2)<<endl;
n=max(N1,N2);
NSD=k;
while(1){
r=n%k;
if(r==0) {cout<<"NSD za III metodom:"<<NSD<<endl<<"L3="<<L3<<endl;break;}
else
{NSD=r;L3++;}
n=k;
k=r;}
f=max(L1,L2);
s=max(f,L3);
cout<<"MAX:"<<s<<endl;
cin>>r1;
if(r1=='k') break;}
}
Результи виконання програми:
/
Висновок. Я засвоїла основні поняття та визначення теорії алгоритмів, проаналізувала вплив параметрів алгоритму на характеристики складності алгоритму
